/*!
  \file bwt.h
  \brief Implementation to encode and decode strings using the Burrows-Wheeler
  algorithms.
  
  The only functions that should be called by the user are bw_c and bw_d; all
  the other functions are used by these two functions, and don't need to be
  called by the user at any time.
*/

#ifndef _BWT_H_
#define _BWT_H_

#include <string.h>

/*Encoding functions*/
int bw_c(char input[], int size, char output[], int *index);
void sort_table(char *table, int len, int start, int end, int *indices);

/*Decoding functions*/
int bw_d(char encoded[], int len, int index, char decoded[]);
void sort_string(char str[], int first, int last);
void compute_alphabet(char sorted[], int len, char alphabet[], int *size);
int binary_search(char alphabet[], int size, char c);

/**
  Computes the Burrows-Wheeler transform for the input string provided.
  \param input - String to be transformed.
  \param size - Size of the string to be transformed.
  \param output - String where the resulting transformation will be returned.
  \param index - Pointer to an integer where the output index of the BWT will
  \return Returns 0 if everything worked correctly; -1 otherwise.
  be returned.
*/
int bw_c(char input[], int size, char output[], int *index)
{
  if (size <= 0)
    return -1;
  
  char *table;
  int *sorted_indices, i;
  
  /*Allocate the necessary memory and check for errors.*/
  sorted_indices = (int*) malloc(sizeof(int) * size);
  if (sorted_indices == NULL)
    return -1;

  /*allocate the memory for the table and check for errors.*/
  table = (char*) malloc(sizeof(char) * ((2*size)+1));
  if (table == NULL)
    return -1;
    
  /*set the indices array, which is used for sorting.*/
  for (i = 0; i < size; ++i)
    sorted_indices[i] = i;
  
  /*Set the representation of the table.*/
  memcpy(table, input, size);
  memcpy(table+size, input, size);
  table[2*size] = '\0';
  
  sort_table(table, size, 0, size-1, sorted_indices);
  
  /*once the table is sorted, build the encoded string and get the index.*/
  for (i = 0; i < size; ++i) {
    if (sorted_indices[i] == 0)
      *index = i;
    output[i] = *(table + sorted_indices[i] + size - 1);
  }
  output[i] = '\0';
  
  /*free the allocated memory.*/
  free(sorted_indices);
  free(table);
  
  return 0;
}

/**
  Sorts the rows in the table in lexicographical order using the merge sort
  algorithm. Note that this function assumes that the parameters are valid; no
  error checking is done.
  \param table - Pointer to an array representing the table whose rows will be
  sorted.
  \param len - Length of the strings in the table.
  \param start - Integer representing index of first row that is being sorted.
  \param end - Integer representing the index of the last row that is being
  sorted.
  \param indices - Array of integers representing the order of the rows after 
  they are sorted.
*/
void sort_table(char *table, int len, int start, int end, int *indices)
{
  int temp_index, *temp_indices;
  int middle, right_count, left_count;
  int i, j, k;
  
  /*Only one item or no items to sort.*/
  if (end <= start)
    return;
  
  /*Two items to sort; just swap them if they're out of order.*/
  if ((end - start) == 1) {
    if (memcmp(table+start, table+end, len) > 0) {
      temp_index = indices[start];
      indices[start] = indices[end];
      indices[end] = temp_index;
    }
    return;
  }
  
  temp_indices = (int *) malloc(sizeof(int) * (end - start + 1));
  if (temp_indices == NULL)
    return;
  
  middle = (start + end) / 2;
  sort_table(table, len, start, middle, indices);
  sort_table(table, len, middle + 1, end, indices);
    
  left_count = middle - start + 1;
  right_count = end - middle;
  i = start;
  j = middle + 1;
  k = 0;  
  while (left_count > 0 && right_count > 0) {
    if (memcmp(table+indices[i], table+indices[j], len) < 0) {
      temp_indices[k] = indices[i];
      --left_count;
      ++i;
    } else {
      temp_indices[k] = indices[j];
      --right_count;
      ++j;
    }
    ++k;
  }
  
  while (left_count > 0) {
    temp_indices[k] = indices[i];
    --left_count;
    ++i;
    ++k;
  }
  
  while (right_count > 0) {
    temp_indices[k] = indices[j];
    --right_count;
    ++j;
    ++k;
  }
  
  k = 0;
  for (i = start; i <= end; ++i) {
    indices[i] = temp_indices[k];
    ++k;
  }
  
  free(temp_indices);
}

/**
  Decodes a string encoded using the Burrows-Wheeler algorithm.
  \param encoded - Encoded string.
  \param len - Length of the encoded string.
  \param index - Index from the Burrows-Wheeler transformation.
  \param decoded - Location where the decoded string will be saved when the
  function is done.
  \return Returns -1 if an error occurred during the process; 0 otherwise.
*/
int bw_d(char encoded[], int len, int index, char decoded[])
{
  char *alphabet, *sorted;
  int i, j, k, symbol_count, sum, *C, *P;
  
  /*Allocate the necessary memory.*/
  alphabet = (char *) malloc(sizeof(char) * (len+1));
  if (alphabet == NULL)
    return -1;
  sorted = (char *) malloc(sizeof(char) * (len+1));
  if (sorted == NULL)
    return -1;
  C = (int *) malloc(sizeof(int) * len);
  if (C == NULL)
    return -1;
  P = (int *) malloc(sizeof(int) * len);
  if (P == NULL)
    return -1;
  
  for (i = 0; i < len; ++i)
    C[i] = 0;
  
  strcpy(sorted, encoded);
  sort_string(sorted, 0, len-1);
  compute_alphabet(sorted, len, alphabet, &symbol_count);
  
  for (i = 0; i < len; ++i) {
    j = binary_search(alphabet, symbol_count, encoded[i]);
    P[i] = C[j];
    ++C[j];
  }
  
  sum = 0;
  for (i = 0; i < symbol_count; ++i) {
    sum += C[i];
    C[i] = sum - C[i];
  }
  
  i = index;
  for (j = len-1; j >= 0; --j) {
    k = binary_search(alphabet, symbol_count, encoded[i]);
    decoded[j] = encoded[i];
    i = P[i] + C[k];
  }
  decoded[len] = '\0';
  
  /*Free the allocated memory.*/
  free(alphabet);
  free(sorted);
  free(C);
  free(P);
  
  return 0;
}

/**
  Sorts the letters in a string in lexicographical order using merge sort. Note
  that the algorithm modifies the string and assumes that the first and last
  indexes passed in the parameters are valid.
  \param str - String whose characters will be sorted. The result will also be
  stored in this parameter.
  \param first - Index where the sorting is starting.
  \param last - Index where the sorting ends.
*/
void sort_string(char str[], int first, int last)
{
  int middle, i, j, k, left_count, right_count;
  char temp, *temp_str;
  
  
  /*Only one item or no items to sort.*/
  if (last <= first) {
    return;
  }
    
  /*Two items to sort*/
  if ((last - first) == 1) {
    if ((str[first] - '0') > (str[last] - '0')) {
      temp = str[last];
      str[last] = str[first];
      str[first] = temp;
    }
    return;
  }
  
  temp_str = (char *) malloc(sizeof(char) * (last - first + 1));
  if (temp_str == NULL)
    return;

  /*Divide the work.*/
  middle = (last + first) / 2;
  sort_string(str, first, middle);
  sort_string(str, middle+1, last);
  
  /*Merge the partial lists.*/
  left_count = middle - first + 1;
  right_count = last - middle;
  i = first;
  j = middle + 1;
  k = 0;
  
  while (left_count > 0 && right_count > 0) {
    if (str[i] < str[j]) {
      temp_str[k] = str[i];
      --left_count;
      ++i;
    } else {
      temp_str[k] = str[j];
      --right_count;
      ++j;
    }
    ++k;
  }
  
  while (left_count > 0) {
    temp_str[k] = str[i];
    --left_count;
    ++i;
    ++k;
  }
  
  while (right_count > 0) {
    temp_str[k] = str[j];
    --right_count;
    ++j;
    ++k;
  }
  
  k = 0;
  for (i = first; i <= last; ++i) {
    str[i] = temp_str[k];
    ++k;
  }
  
  free(temp_str);
}

/**
  Computes the alphabet from a sorted string.
  \param sorted - Input string, sorted.
  \param len - Length of the input string.
  \param alphabet - String where the alphabet will be stored.
  \param size - Pointer to an integer where the number of symbols in the
  alphabet will be stored.
*/
void compute_alphabet(char sorted[], int len, char alphabet[], int *size)
{
  int i, j;
  
  alphabet[0] = sorted[0];
  j = 1;
  for (i = 1; i < len; ++i) {
    if (sorted[i] == alphabet[j-1])
      continue;
    alphabet[j] = sorted[i];
    ++j;
  }
  alphabet[j] = '\0';
  *size = j;
}

/**
  Searches for a character c in a sorted list.
  \param alphabet - Sorted list of characters.
  \param size - Number of symbols in the alphabet.
  \param c - Character to search for.
*/
int binary_search(char alphabet[], int size, char c)
{
  int min, max, mid;
  
  min = 0;
  max = size - 1;
  
  while (1) {
    mid = (min + max) / 2;
    if (c == alphabet[mid])
      return mid;
      
    if (c > alphabet[mid])
      min = mid + 1;
    else
      max = mid - 1;
      
    if (min > max)
      break;
  }
  
  return -1;
}

#endif

